import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/11/16
 * Time: 02:51
 */
public class Solution {
    /*public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        ListNode pre = lists[0];
        for(int i = 1;i < lists.length;i++){
            ListNode cur = lists[i];
            pre = mergeTwoLists(pre,cur);
        }
        return pre;
    }
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        if(headA == null && headB == null) return null;
        if(headA == null && headB != null) return headB;
        if(headA != null && headB == null) return headA;
        ListNode newHead = new ListNode(-1);
        ListNode temp = newHead;
        while(headA != null && headB != null){
            if(headA.val >= headB.val){
                temp.next = headB;
                headB = headB.next;
            }else{
                temp.next = headA;
                headA = headA.next;
            }
            temp = temp.next;
        }
        while(headA != null){
            temp.next = headA;
            headA = headA.next;
            temp = temp.next;
        }
        while(headB != null){
            temp.next = headB;
            headB = headB.next;
            temp = temp.next;
        }
        return newHead.next;
    }*/
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for(ListNode cur : lists){
            if(cur != null){
                heap.offer(cur);
            }
        }
        ListNode result = new ListNode(-1);
        ListNode pre = result;
        while(!heap.isEmpty()){
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = pre.next;
            if(cur.next != null){
                heap.offer(cur.next);
            }
        }
        return result.next;
    }
}
